package com.zj.leetcode.hard.dynamicProgramming;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 买卖股票的最佳时机 IV
 * 188 best-time-to-buy-and-sell-stock-iv
 * @author: Zhang Bo
 * @create: 2022-05-10 11:16:03
 **/
public class BestTimeToBuyAndSellStockIv {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockIv().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * f(n) = f(n - 1)
         *
         * @param k
         * @param prices
         * @return
         */
        public int maxProfit(int k, int[] prices) {

            //TODO 待学习
            int[] buy = new int[k+1];
            int[] sell = new int[k+1];
            Arrays.fill(buy, Integer.MIN_VALUE);
            Arrays.fill(sell, 0);

            for (int p: prices) {
                for (int i = 1; i <= k; i++){
                    buy[i] = Math.max(buy[i], sell[i - 1] - p);
                    sell[i] = Math.max(sell[i], buy[i] + p);
                }
            }
            return sell[k];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}